/*
2021-11-20
https://www.acwing.com/problem/content/4077/
*/
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=405;
int g1[N][N],g2[N][N];
int n,m;
int a,b;

int floyd(int g[][N])
{
    if(g[1][n]==1) return 1;
    
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
            
    return g[1][n];
}

int main()
{
    cin>>n>>m;
    
    memset(g1,0x3f,sizeof g1);
    memset(g2,0x3f,sizeof g2);
    
    while(m--)
    {
        cin>>a>>b;
        g1[a][b]=1;
        g1[b][a]=1;
    }
    
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j && g1[i][j]!=1)
                g2[i][j]=g2[j][i]=1;
        
    a=floyd(g1),b=floyd(g2);
    int res=max(a,b);
    if(res==0x3f3f3f3f) res=-1;
    cout<<res<<endl;
    
    return 0;
}
